import javax.swing.*;
import java.util.ArrayDeque;

public class SortTest {
    public static void main(String[] args) {

        //插入排序insertion sort  思路：逻辑上分为无序表和有序表，每次从无序表中取第一个元素，在有序表中找到它的位置后插入。
        //刚开始，第一个元素默认为是有序的
        //int[] arr={9,1,2,5,7,4,8,6,3,5};

        int[] arr=new int[80000];

        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int)(Math.random()*80000);
        }
        int left=0,right=arr.length-1;
          //第一轮: 8 23 |  4 11 0 7 3
          //第二轮：4 8 23 | 11 0 7 3
      /*  for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println("排序后的结果");*/

        //测试速度
        Long start=System.currentTimeMillis();

        QuickSort(arr,left,right);

        Long end=System.currentTimeMillis();
        System.out.println("执行的时间为："+(end-start)+"毫秒"); // 冒泡排序：12451 12661 12903选择排序：3416 3626 3600
                                                                  //插入排序1：3625 3586 4400 插入排序2：2231 2250 2263
       /* for (int i = 0; i < arr.length; i++) {                      //  插入排序3:2297毫秒 2222毫秒 2206毫秒
                                                                  //希尔排序交换法：5935毫秒  6083毫秒 5923
                                                                  //希尔排虚移位法：25毫秒 19毫秒 16毫秒
                                                                  //快速排序：51毫秒  23毫秒 24毫秒 40毫秒 39毫秒
            System.out.print(arr[i]+" ");
        }*/



    }
    //冒泡排序(改进)--》平均12.7秒钟-->8万个数据
    public static int[] BubbleSort(int[] arr){//23,8,19,4,100,11,0,54,7,63,3
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag=true;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i]>arr[j]){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    flag=false;
                }
            }
            //改进
            if(flag){
                break;
            }
        }
        return arr;
    }
    //选择排序---3.5--8万个数据
    public static int[] SelectSort(int[] arr){
        //选择排序--》第一轮：在0-n中选择最小,与第一个位置上的元素交换
                  // 第二轮：在1-n中选择最小，与第二个位置上元素交换
        for (int i = 0; i < arr.length-1; i++) {
            //10 1 2 3 8 5 19 13
            int minIndex=i+1;//用于记录最小值的索引--用于交换
            int min=arr[i+1];//用于记录后面序列的最小值--是因为后面可能还会有更小的值--也是为了记录索引
            for (int j = i+1; j < arr.length; j++) {
                if (min > arr[j]) {
                  //23,8,19,4,100,11,0,54,7,63,3
                    min=arr[j];
                    minIndex=j;
                }
            }
            //再将找到的最小值放到正确的位置上,交换元素
            if(arr[i]>arr[minIndex]){//关键点，最后还要判断，只有数更小才会交换
                int temp=arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
        }
        return arr;


    }

    //插入排序（直接交换数据）--6.5秒--8万个数据
    //插入排序（赋值交换数据，不是找到一个小的值就将它交换）--2秒--8万个数据
    public static int[] InsertionSort(int[] arr) {//交换的速率很慢，改为赋值交换数据。
        for (int i = 0; i < arr.length-1; i++) {
            int poIndex=i;//中间指针-->倒着查找有序表中，要插入的位置
            int unOrder=arr[i+1];//先记录无序列表的第一个要查找的值
            //在这里还要进行判断--》如果无序表的第一个元素的值大于有序表最后一个元素值，就不需要查找了
            if(unOrder>=arr[i]){
                continue;
            }
            for(int j=i;j>=0;j--){
                if(unOrder<arr[j]){
                    //8 19 19 23， 9 100
                    poIndex=j;
                    arr[poIndex+1]=arr[poIndex];
                    arr[poIndex]=unOrder;
                }
            }

        }
        return arr;

    }

    public static int[] InsertionSort2(int[] arr){

        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
//定义待插入的数
            insertVal = arr[i];
            insertIndex = i - 1; // 即 arr[1]的前面这个数的下标
// 给 insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给 insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将 arr[insertIndex] 后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
                insertIndex--;
            }
// 当退出 while 循环时，说明插入的位置找到, insertIndex + 1
// 举例：理解不了，我们一会 debug
//这里我们判断是否需要赋值
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }

        }
        return arr;
    }

    //插入排序--》平均2.2秒排序8万个数据
    public static int[] InsertionSort3(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
          /*  ===思路：每次从无序表中取第一个数，到有序表找，找到了后就插入，不能交换，通过移动位置实现交换，而且是倒着移动，因为
          要是从前往后移动会使得移动大量数。

          =====过程分析：

     1、不能交换（例如：1 2 5 8 | 3，11----》交换：1 2 3 8 |5 11--》可以看出若交换了，就相当于把排好的有序表的数又放到了无序表中）
     2、倒着移动位置交换 (例如：1 2 5 8 | 3，11----》比如现在找3的位置，3的值已经记录在了unOrderVal中，先移动8覆盖掉下个位置上的数
     变成 1 2 5 8|8,11 然后将8的最初位置给待插入的数unOrderVal，变成：1 2 5 3|8 11 ；现在接着比较-》3<5 将5移动 1 2 5 5|8 11
     然后将3放到5原来的位置上-》1 2 3 5 |8 11）
     3、建议使用while循环，因为可以减少不必要的比较次数。要倒着找，因为可以避免移动大量的数。
           */
            int orderIndex=i;//无序表的第一个数的索引，
            int unOrderVal=arr[i+1];//无序表的第一个数
            while(orderIndex>=0 && unOrderVal<arr[orderIndex]){
                //这里进行有序表的数字移动
                arr[orderIndex+1]=arr[orderIndex];
                arr[orderIndex]=unOrderVal;
                orderIndex--;
            }
        }
        return arr;

    }

    //希尔排序--交换法---》5.98秒--8万个数据
    public static int[] ShellSort(int[] arr){
        //这个循环用于表示趟数--》10个数：趟数：5 2 1（3趟）
        int len=arr.length;
        int temp=0;
        for(int trip=len/2;trip>0;trip/=2){

            //这个循环用于表示每趟需要比较的组数：（第一个数不用比较，第一个数默认是有序的）
            // 第一轮--》5组，第二轮：8组 第三轮：9组。可以想下之前排序的时候都不考虑最后一个数。因为只要其他位置的数排好了
            //那么它的位置一定是正确的。
            for(int i=trip;i<len;i++){

                for(int j=i-trip;j>=0;j-=trip){
                    //判断是否交换
                    if(arr[j]>arr[j+trip]){
                        temp=arr[j];
                        arr[j]=arr[j+trip];
                        arr[j+trip]=temp;
                    }
                }

            }
        }
        return arr;

    }


    //希尔排序--移位法--平均0.02秒-8万个数据
    public static int[] ShellSort2(int[] arr) {
        //这个循环用于表示趟数--》10个数：趟数：5 2 1（3趟）
        int len = arr.length;
        int temp = 0;
        for (int trip = len / 2; trip > 0; trip /= 2) {
            for (int i = trip; i < len; i++) {
                int tempIndex = i;
                int unOrderVal = arr[i];//记录待插入的值
                if (arr[i] < arr[tempIndex - trip]) {
                    //找位置
                    while (tempIndex - trip >= 0 && unOrderVal < arr[tempIndex - trip]) {
                        arr[tempIndex] = arr[tempIndex - trip];
                        arr[tempIndex - trip] = unOrderVal;
                        tempIndex -= trip;//和插入排序的逻辑相同，只是多了步长（两个数的间隔）而已。
                    }
                }

            }
        }
        return arr;
    }

    //快速排序--35.4毫秒--8万个数组

    public static void QuickSort(int[] arr,int left,int right){
        if(left>=right){
            //递归结束条件
            return;
        }
        int l=left,r=right;
        int base=arr[left];//基准数
        while(l<r){
            while(l<r && arr[r]>=base){
                r--;
            }
            while(l<r && arr[l]<=base){
                l++;
            }
            if(l>=right){

                break;
            }

            //交换
            exchange(arr,l,r);

        }
        //此时left==right,交换基准数和right后left都一样
        exchange(arr,left,l);//这里的left就是基准数的索引。
        if(r==l){
            r--;
            l++;
        }
        //向左区间递归
        QuickSort(arr,left,r);
        //向右区间递归
        QuickSort(arr,l,right);

    }
    //交换方法
    public static void exchange(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }


}
